// ALERT: 本代码中涉及的数组，是一维动态数组，。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	//整型指针
	ElemType *elem;
	//存储动态数组里边元素的个数
	int TableLen;
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 查找结点
int Search_Seq(SSTable ST, ElemType key) {
	// NOTE: 临时变量初始化
	// STEP: 让零号元素作为哨兵
	// HINT: 哨兵的值是没有实际意义的。但引入哨兵的目的是为了当遍历到哨兵处，就应该结束遍历。
	ST.elem[0] = key;

	// STEP: 目标元素索引值
	int i;


	// NOTE: 遍历顺序表，得到目标元素索引值
	for (i = ST.TableLen - 1; ST.elem[i] != key; --i);


	// NOTE: 返回目标元素索引值
	return i;
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 折半查找
// ALERT: 这里不考虑哨兵问题。即：所有数组元素都是有效的。
//  以下算法认为数组中的数值按照从小到大的顺序排列。
int Binary_Search(SSTable L, ElemType key) {
	// NOTE: 变量初始化
	int low = 0, high = L.TableLen - 1, mid;


	// NOTE: 进行折半查找（前提：low <= high）
	while (low <= high) {
		// STEP: 确认中间值mid的索引
		mid = (low + high) / 2;

		if (L.elem[mid] == key)
			// STEP: 若中间值与查找关键字key相等，则认为是找到了
			return mid;
		else if (L.elem[mid] > key)
			// STEP: 若中间值与查找关键字key大，则待查数应在较小的半区。则应将下限low移动到mid的旁边（较小数的一侧）
			high = mid - 1;
		else {
			// STEP: 若中间值与查找关键字key小，则待查数应在较大的半区。则应将下限low移动到mid的旁边（较大数的一侧）
			low = mid + 1;
		}
	}


	return -1;
}

// FUNCTION：自定义比较函数compare，以实现
// @param: 用于left，right是任意两个元素的地址值
int compare(const void *left, const void *right) {
	return *(ElemType *) left - *(ElemType *) right;

	// NOTE: 按照从大到小排列
	// return *(ElemType*)right - *(ElemType*)left;

	//
	// REVIEW: 上述代码可以展开来写方便看懂。
/*
	int *pleft = (int *)left;
	int *pright = (int *)right;

	int num_left= *pleft;
	int num_right = *pright;

	return num_left - num_right;
*/
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明用于数组元素值的中间变量
	ElemType key;

	// STEP: 声明用于存储查询元素的位置
	int pos;


	// NOTE: 数组元素赋值
	ST_Init(ST, 10);
	// 验证赋值情况
	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 二分查找
	// ALERT: 由于二分查找必须保证数组内元素的大小是递增或递减的，所以此处提前引入快速排序的概念
	// STEP: 使用快排qsort，实现对数组元素的整理
	// @param:
	//  Base：表示需要排序的数组始址
	//  NumOfElements：表示数组中元素个数
	//  SizeOfElements：表示每一个元素所占空间大小
	//  PtFuncCompare：表示自定义的比较规则，通常用数组名代替
	printf("After sorting, sequence is: ");
	qsort(ST.elem, ST.TableLen, sizeof(ElemType), compare);
	ST_print(ST);

	// STEP: 输入需要查找的数值key
	printf("Perform binary search. Please input the \"key\" value: ");
	scanf("%d", &key);

	// STEP: 执行二分查找函数，返回元素key的位置信息
	pos = Binary_Search(ST, key);
	if (pos != -1) {
		printf("Query success. Its position is %d.\n", pos);
	} else {
		printf("Query fail!\n");
	}


	// NOTE: 返回值
	return 0;
}
